perm filename WCCF.3[P,JRA] blob
sn#556270 filedate 1981-01-12 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00002 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 NATURAL LANGUAGE ACCESS TO DATABASE MANAGEMENT SYSTEMS
C00042 ENDMK
C⊗;
NATURAL LANGUAGE ACCESS TO DATABASE MANAGEMENT SYSTEMS
Bil Lewis 325 Central, Menlo Park, Ca 94025
Abstract
A brief description of natural language and computational
linguistics is given below. This is followed by a short analysis
of some of the problems faced in machine language understanding
systems and an examination of some of those systems developed at
SRI. The talk is concluded with a demonstration of one of those
systems.
A Little Computational Linguistics
One of the questions faced by linguistics is "What is an
acceptable sentence in the language?" [I will assume that we are
dealing strictly with typed text, no sounds, gestures &c.] The
answer must lie with the speakers of the language in question (for
my purposes, English), there being no a priori definition of the
language. I should point out, that contrary to what English
grammar teachers may imply, there does not exist a comprehensive
grammar of the language.
By asking people who speak the language (keeping in mind
that it is also difficult to decide who is or is not a speaker of
"standard English") we find that there is a core of sentences that
most everyone will accept, a fringe that some will and some won't,
and the rest of the possible sentences that few or no speakers
accept.
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
! Sandy didn't kiss Kim.
? Sandy ain't kissed Kim.
* Sandy Kim kissed no.
Figure 1
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
Much effort has been put into trying to decide just what
should and shouldn't be accepted in a "standard English". In our
work this problem takes on great importance because we are going
to have to write functions to analyse whatever we decide to
accept. Admitting limited resources, we restrict the problem to a
practical one: "What do we have to accept to cover a reasonable
subset of the language (so that people can use fairly a natural
conversational style), and what do we reject because it will take
so much time or space?"
Our coverage should be sufficent to accept and
"understand" many different ways of saying the same thing, and
there are many ways. Unfortunately, as we increase the coverage,
we increase the amount of ambiguity in a sentence. If we allow
prepositional phrases to modify either nouns or verbs, then what
is the proper meaning to the sentence: "I hit the dog with the
stick" -- did I use the stick to strike the dog, or did the dog
have the stick in its mouth when I struck it? This is only a very
obvious example, a machine trying to understand a sentence
!
typically generates dozens of much more subtle ambiguities which
must be resolved, and that takes time.
Phrase Structure Grammars (PSG)
In dealing with something as complicated as language, it
is useful to be able to assign it a structure, and deal with with
a known structure rather than just a list of words. To do this,
we use PSGs to define the structure that a sentence is going to
have to fit into. [There are many variations on PSGs, but I will
stick with these as they are what are being used exclusively at
SRI.] Simply put, a PSG is a set of (context free) rules that
tell us what a given part of speech is allowed to consist of.
Below is a simplified PSG:
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
<SENTENCE> ==> <NOUN.PHRASE> <VERB.PHRASE>
<VERB.PHRASE> ==> <VERB> ( <NOUN.PHRASE> )
<NOUN.PHRASE> ==> ( <DETERMINER> ) ( <ADJECTIVE> ) <NOUN>
<NOUN> ==> "Kim" "Who" "blue" "love" "Fox"
<VERB> ==> "eat" "command" "love" "be"
<ADJECTIVE> ==> "blue" "big"
<DETERMINER> ==> "the" "a" "an"
<SENTENCE>
/ \
/ \
<NOUN.PHRASE> <VERB.PHRASE>
| / \
| <VERB> <NOUN.PHRASE>
| | / \
| | <DETERMINER> <NOUN>
| | | |
WHO COMMANDS THE FOX
Figure 2
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
The process of deciding what the proper structure of a
sentence is is called "PARSING", and the result of the parse is a
"PARSE TREE" such as shown above. Once a parse tree is derived
(and there may be more than one) for a sentence, we can turn to
the problem of deciding what the sentence "means".
Parsers
There are almost as many different parsers in existance as
there are second year grade students in computer science. They
operate top-down, botton-up, left-to-right, right-to-left,
island-out, edges-in, and any combination of these. I will
briefly discuss the two in use at SRI.
LIFER [1] is a single pass, top-down, left-to-right parser
that has been in use for at least eight years. It is well tested,
and is used as the foundation for many natural language systems.
It takes a sentence as input and produces a parse tree as above.
At each node in the tree the system designer may define a function
to be evaluated whose result will be passed up the tree to the
dominating node for further processing. At the top of the tree
(the end of the parse), the final result is returned to the
calling function. This result might be a set of instructions to
do something, a database query, or a response to the user.
!
Because LIFER only has a single pass, and returns just the
result of the parse (and not a parse tree), it is normally used in
conjunction with a "SEMANTIC GRAMMAR" which does the semantic
analysis along side of the syntactic analysis. A semantic grammar
is characterized by consisting of categories and rules that refer
directly to the domain of discourse, and leaves no room for
consideration of anything outside of it. This has the advantage
of reducing ambiguity (hence speeding up the parsing), but it
locks one firmly into the one domain in question, making it very
difficult to transport the work to another domain.
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
<WHO.QUESTION>
/ \
/ <WHO.SENTENCE>
/ / \
/ <ACT.VERB> <SHIP>
/ | / \
| | / <SHIP.NAME>
| | | |
WHO COMMANDS THE FOX
Figure 3 (A typical parse tree for a semantic grammar)
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
The other parser, which is being used, is DIAMOND, a
bottom-up, left-to-right parser that performs three passes. The
first pass constructs an annotated syntatic parse tree, the second
attachs the semantics to this tree (this time working top-down),
and the third does whatever remains to be done, pronoun
resolution, quantifier scoping &c.
A diamond parse tree is shown in figure 2. It is
distinguished from the LIFER parse tree by consisting only of
syntatic categories which would be identical for a similar
question in any domain (eg. "Who waters the garden?"). Such a
grammar gives us the reciprocal attributes of the semantic grammar
above: it is domain independent and easy to transport, but is more
difficult to write, finds much more ambiguity, and is slower.
Natural Language Systems
Starting with the advant of digital computers in the late
50s, a large number of natural language understanding systems have
been written to address many different domains and problems.
STUDENT solved high school algebra problems, BASEBALL did
elementry database access, SAD SAM performed deductions upon a
network concerning familial relationships, PARRY tried to imitate
a parinoid, ELIZA a psychiatrist; there were attempts at
translating between languages (eg. French-English), attempts to
carry on meaningful dialogues, and myrid other applications.
For the most part, these systems saw limited success in
their restricted domains, were exercised only by their creators,
and died quiet deaths at the completion of their funding. Either
their domains were so limited as to make them totally useless, or
they proved so inadaquate to the task at hand that they were of no
practical value.
In the latter case the problem often stemmed from the fact
that the systems were unable to build a model of the conversation
that they were attempting to take part in. They could not
"understand" what was happening well enough to establish a context
!
in which to consider the sentences that they were reading.
Analogous to the way in which the word "bank" can be a financial
institution or the edge of a river depending upon the context of
the sentence, a sentence in turn can depend on the context of its
enviroment for its intended meaning.
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
WHO ARE THE COMMANDERS OF THE US SUBS?
This question alone would require listing all 147 of them.
Whereas in the context below:
WHAT NAVAL VESSELS ARE IN THE MED?
WHO ARE THE COMMANDERS OF THE US SUBS?
the desired answer would be just those in the Mediterranean sea.
Figure 4
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
In general such problems are too difficult to overcome at
present (the one above represents the leading edge of present
research) and any domain that requires successful handling of them
are beyond our grasp. Let us then retreat from the general
problem and focus our attentions upon some of the narrower domains
where there is some hope of addressing meaningful problems with
little or no requirement to establish a context for the discourse.
Natural Language Access to Databases
Computers have been used for years in data base management
to provide the raw (or slightly processed) information by which
decisions are regularly made. People are used to making requests
for information which assume no more context than the fact that
they are working with a certain database. Normally they formulate
their question and give it to a computer specialist to write the
database query and they expect results in terms of tables or
statistics. Here the computer specialist is being asked to obtain
data from the machine in various forms, but NOT to provide answers
to important questions. The lack of discourse to be considered,
and the simplicity of the expected answers make database access a
good subject for language understanding.
By raw data we mean the answers to such questions as:
HOW MANY AIRCRAFT ARE WITHIN 200 MILES OF LUANDA?
HOW LONG WILL IT TAKE TASK FORCE 3 TO REACH LUANDA?
both of which can be easily answered by a machine while the
important question might be:
SHALL WE PREVENT THE CUBAN INVASION OF ANGOLA?
Because no one is asking the DBMS to answer the hard
questions, it is feasible to eliminate the intermediate step of
routine coding by specialists if the machine is capable of giving
the same answers by understanding questions posed in English. Many
hours have been spent in designing systems which do a good job of
understanding English questions about a given data base.
LADDER: Language Access to Distributed Data with Error Recovery
The LADDER [4] system, developed at SRI over the past six
!
years, is a excellent example of a hand-coded Natural language
access to database system. The US navy has large amounts of
information concerning ships, their capabilities, movements &c.
scattered across the nation on a number of different computers.
The LADDER system allows officers to query the different computers
in English without being concerned with either the actual location
of the computers being used, or the structure of the data on those
machines.
LADDER can handle a rather wide range of questions about
the data in the navy's "BLUE FILE", some typical questions it
handles are in figure 5.
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
HOW FAR IS THE CONSTELLATION FROM CHARLESTON?
WHERE IS THE LOS ANGLES?
WHERE IS THE LONGEST SHIP CARRYING VANADIUM ORE?
WHEN WILL THE PHILADELPHIA REACH PORT?
WHAT US SHIPS ARE WITHIN 400 MILES OF GIBRALTAR?
WHAT SHIPS FASTER THAN THE KENNEDY ARE WITHIN 500 MILES OF NAPLES?
Figure 5
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
Roughly LADDER is constructed in the shape of figure 6.
Questions by the users are analysed by the Language Executive,
using the grammar rules and the information in the lexicon about
the words. The result is a general database query (in the SODA
query langauge) which is passed to the next component which knows
what database information is contained where and directs the
database queries (appropriately translated into the respective
database language -- there are several in use) to the machine
containing that information. The results are returned a tabular
form to the user.
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
*** *
←←←←←←←←←← ←←←←←←←←←←← ←←←←←←←←←←
|Lexicon | | | | |
| | | dB | | |
|Grammar | |Structure| | DBMS's |
USER <====> | Rules | <==> | |<===>| |
| | |Reasoning| | |
| Exec | | System | | |
---------- ----------- ----------
English SODA Data-language
Figure 6
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
The LADDER system is based on the LIFER parser and, as it
is directed towards a single well-defined database, it is able to
make extensive use of the semantic nature of its grammar (figure 3
is a slightly simplified example of a LADDER parse tree), and
refers to ships, commanders, and oceans as parts of the grammar.
The analysis of a sentence depends heavily upon this fact, which
serves to limit the possible interpretations of a sentence.
In the sentence: "WHAT SHIPS WITH DOCTORS ARE THERE?"
LADDER knows immediately that it can build part of a SODA query to
represent the noun phrase: ((DOCTOR S) EQ TRUE). The remainder of
the question: "WHAT -- ARE THERE" asks which ships these are, and
!
LADDER knows to return the name of the ship in such cases: (IN S
SHIP.FILE ((DOCTOR S) EQ TRUE) (? (NAME S))).
The stars above the diagram in figure 6 illustrate the !
expertise required of the person to change the two modules. It is
not terribly difficult to inform the file manager that a new
database has been added on a different machine, nor that the
structure of a certain data file has been changed, but to change
the grammar requires a wizard of high rank. Three star wizards
capable of doing such work are so few in number and in such great
demand that it is impossible for them to write similar systems for
other database domains. The solution is to build a system which
can build the appropriate structures itself, which brings me to
the system I wish to demonstrate:
D-TED: A Diamond-based Transportable Data Manager
To accomplish the objective of easy transportability,
D-TED [2] is based on a syntatic grammar, DIALOGUE [3], which is
parsed by the DIAMOND parser to yield an annotated parse tree and
a predicate calculus formula translation of the English sentence.
In contrast to LADDER, in which the notion of the Blue file is
implicit, D-TED represents any individual table in a relational
database explicitly as a directed graph known as a conceptual
schema. In D-TED it is the notion of a relational database that
is implicit.
The type of relational database that D-TED "understands"
is fairly strictly limited, and violation of these style
constraints results in a situation where "talking" about the
database is awkward and stilted (We are working to expand the
conceptual coverage of different relational databases, but that's
still in the future). D-TED expects a table to to be a list of
descriptions of some sort of concrete entity such as a ship,
person, or store. What it is ill-equipted to handle are such
abstract concepts as time dependent events or multiple entries of
an entity which varies a single parameter.
To acquire a table, D-TED asks the user to give the table
a name (arbitrary), to name the entity being described, to list
the attributes of the table, synonyms for them, and to categorize
each attribute as being arithemtic, boolean, or symbolic. With
this information, D-TED creates a conceptual schema for the
database and adds the terms listed by the user to the lexicon. To
do this, the user needs no linguistic background beyond the
ability to speak English fluently.
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
PERSON.TABLE STORE.TABLE
←←←←←←←←←←←←←←←←←←←←←←←←←←←←← ←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
NAME AGE SEX STORE NAME OWNER CITY #EMPLOYEES
Kim 27 F ANN'S ANN'S Ann PAO 12
Ann 39 F ANN'S PETE'S Pete MP 11
Pete 25 M PETE'S
PERSON / PEOPLE / EMPLOYEE STORE / SHOP
AGE: OLD (ER, EST), YOUNG (ER, EST) CITY: PAO = Palo Alto,
SEX = GENDER: F = FEMALE, M = MALE MP = Menlo Park
Join on: PERSON.TABLE(STORE) = STORE.TABLE(NAME)
PERSON.TABLE(NAME) = STORE.TABLE(OWNER)
Figure 7
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
!
Additional lexical entries are made when information is
being put into the database in symbolic attributes, thus Kim, Ann,
PETE'S, and Palo Alto are placed into the lexicon so that the user
may refer to them. In cases where the database is very large and
core space is limited, the user may decide not to put put all the
proper nouns into the lexicon, leaving us with the so-called
Proper Noun problem. In D-TED the solution has been to allow the
user to refer to noun in question with its type (ie "How fast is
the ship JFK" vs "How fast is the JFK") to disambiguate it. This
is not a perfect solution, but under the circumstances it is
adaquate.
Once the schema for a table is defined, it is possible to
define a set of verbs which relate to the attributes of the table.
The user is guided through a series of questions which allow D-TED
to decide which of the 13 verb patterns of English it belongs.
At this point the user is able to ask question of D-TED in
a subset of English, and to tell D-TED to make changes to the
database (figure 8). Being only an experimental prototype system,
D-TED does not handle as wide a range of sentences as one would
like, but even naive users have been able to phrase most of their
questions in a recognizable form without undue difficulty. More
conspicuously absent (and more difficult to address) are the
enhancement functions such as LADDER uses to define the bounderies
of an ocean. As of yet I do not know of a good solution short of
employing a programmer.
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
Transportable English-based Data-access
-- SRI International --
Type a question or command. After any ">" type "?" for help.
1> NEW
The name of the new file is (type file name) > PERSON.TABLE
The fields of file PERSON.TABLE are (type sequence of fields)
> NAME AGE SEX STORE
What names do you want to use to refer to a subject of the PERSON.TABLE
file? > PERSON PEOPLE EMPLOYEE
.
.
.
AGE is:
1 an arithmetic field (values may be added, subtracted etc.)
2 a feature field (values are Boolean, T or F, YES or NO ...)
3 a symbolic field (values are usually nouns or adjectives)
(Please type 1, 2, or 3) > 1
If there is a word wwww such that the question
HOW wwww IS THE PERSON ?
is equivalent to
WHAT IS THE AGE OF THE PERSON ?
please type wwww (else type <CR>). > OLD
If there are antonyms for OLD, please list them (type a sequence
of words and multiwords) > YOUNG
.
.
. !
Type a question or command. After any ">" type "?" for help.
4> HOW MANY STORES ARE THERE
The Answer is CNT equals 2
9> WHO IS THE OWNER OF PETE'S
10> HOW OLD ARE THE FEMALE PERSONS
11> WHO ARE THE PEOPLE IN PALO ALTO
12> HOW MANY PEOPLE ARE THERE THAT ARE OLDER THAN KIM AND ARE IN MENLO
PARK
13> WHAT IS THE STORE OF THE OLDEST PERSON
14> LIST THE NAMES OF THE PEOPLE WITH AGE BETWEEN 22 AND 35 TABULATED
BY SEX AND CITY
------------------
|SEX |CITY |NAME| **Note that SEX is alphabetized**
|-----|-----|----|
|F |PAO |KIM |
|M |MP |PETE|
------------------
15> WHICH EMPLOYEES ARE IN FRED'S SHOP **The Proper Noun problem**
FRED'S is a STORE in the file PERSON.TABLE (YES or NO) > YES
*****************************NO DATA AVAILABLE*************************
Figure 8 (An edited transcript from D-TED)
←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
In the comming years I expect to see programms emerge
which will effectively overcome the problems of discourse,
knowledge representation, and deduction. Those will all be quite
some time in comming though, perhaps twenty or thirty years for
them to be openly avaliable. Database access systems on the other
hand are here now. In the next five to ten years systems such as
D-TED will be used for data management in businesses large and
small, providing information at a fraction of the present cost.
REFERENCE
1. G. G. Hendrix, "The LIFER Manual: A Guide to Building Practical
Natural Language Interfaces," SRI Artificial Intelligence
Center Tech. Note 138, SRI International, Menlo Park,
California (February 1977).
2. B. Lewis, TED: "A Transportable English Data Manager" SRI
Artificial Intelligence Center Project report 7910, SRI
International, Menlo Park, California (October, 1979)
3. J. Robinson, "Diagram: A Grammar for Dialogues" SRI Artificial
Intelligence Center Tech. Note 205, SRI International, Menlo
Park, California (February, 1980)
4. E. Sacerdoti, "Language Access to Distributed Data with Error
Recovery," Proc. 5th International Joint Conference on
Artificial Intelligence, Cambridge, Massachussetts,
(August 1977).
!
-------